package leetcode_周赛._2023._05;

/**
 * 第 346 场周赛
 * <p>AC_3</p>
 *
 * @author yezh
 * @date 2023/5/21 14:10
 */
public class _21 {

    /**
     * 2698. 求一个整数的惩罚数
     * 算法: 回溯
     */
    public int punishmentNumber(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int num = i * i;
            if (check(num + "", 0, 0, i)) {
                ans += num;
                System.out.println(num);
            }
        }
        return ans;
    }

    boolean check(String num, int start, int cur, int target) {
        if (start == num.length()) return cur == target;
        int tmp = 0;
        for (int i = start; i < num.length(); ++i) {
            tmp = tmp * 10 + (num.charAt(i) - '0');
            if (tmp > target) return false;
            if (check(num, i + 1, tmp + cur, target)) return true;
        }
        return false;
    }

}
